package com.company.Tree;
import java.io.*;
import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}22:58
 */
public class HuffmanCode {
    public static void main(String[] args) {
//        String content = "i like like like java do you like a java";
//        byte[] contentBytes = content.getBytes();
//        System.out.println(contentBytes.length);
//        System.out.println(Arrays.toString(huffmanZip(contentBytes)));
//        //压缩文件===================================================
//        String srcFile = "C:\\Users\\VX5\\Desktop\\test.bmp";
//        huffmanFile(srcFile);
        //测试压缩文件
//        String src = "C:\\Users\\VX5\\Desktop\\test2.bmp";
//        String dst = "C:\\Users\\VX5\\Desktop\\dst.zip";
//        zipFile(src,dst);
//        System.out.println("压缩成功");

        //测试解压
        String zipFile = "C:\\Users\\VX5\\Desktop\\dst.zip";
        String dstFile = "C:\\Users\\VX5\\Desktop\\src.bmp";
        unZipFile(zipFile,dstFile);
        System.out.println("解压成功");
    }


    /**
     * 哈夫曼编码封装
     * @param contentBytes
     * @return
     */
    public static byte[] huffmanZip(byte[] contentBytes){
        List<Node> nodes = getNodes(contentBytes);
        System.out.println(nodes);

        System.out.println("哈夫曼树");
        Node huffamnTreeRoot = creatHuffmanTree(nodes);
        System.out.println("前序遍历");
        huffamnTreeRoot.preOrder();

        //测试哈夫曼编码
        getCodes(huffamnTreeRoot);
        System.out.println(huffmanCodes);

        byte[] huffmanCodeBytes = zip(contentBytes,huffmanCodes);
        System.out.println(Arrays.toString(huffmanCodeBytes));

        byte[] b = decode(huffmanCodes,huffmanCodeBytes);
        System.out.println("原来的字符串"+new String(b));
        return huffmanCodeBytes;
    }

    public static void huffmanFile(String srcFile){
        String dstFile = "C:\\Users\\VX5\\Desktop\\dst.zip";
        zipFile(srcFile,dstFile);
        System.out.println("压缩成功");
    }

    //编写一个方法，完成对压缩数据的解码
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //先得到huffmanBytes对应的二进制字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length;i++){
            //判断是不是最后一个字节
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag,b));
        }
        System.out.println("stringBuilder="+stringBuilder.toString());

        Map<String,Byte> map = new HashMap<>();
        for (Map.Entry<Byte,String> entry:huffmanCodes.entrySet()){
            map.put(entry.getValue(),entry.getKey());
        }
        System.out.println(map);
        //创建一个集合存放Byte
        List<Byte> list = new ArrayList<>();
        //i 可以理解成索引，扫描StringBuilder
        for (int i = 0; i < stringBuilder.length();){
            int count = 1;//小的计数器
            boolean flag = true;
            Byte b = null;

            while (flag){
                //取出一个字符'1''0'
                String key = stringBuilder.substring(i,i+count); //i不动，让count移动，直到匹配到一个字符
                b = map.get(key);
                if (b==null){
                    count++;
                }else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;//i直接移动到count
        }
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++){
            b[i] = list.get(i);
        }
        return b;
    }

    //将一个byte转成一个二进制字符串

    /**
     * 标志是否需要补高位如果为true,表示需要补高位、如果是false表示不补，如果是最后一个字节，无需补高位
     * @param flag
     * @param b
     * @return
     */
    private static String byteToBitString(boolean flag,byte b){
        int temp = b;
        if (flag){
            temp |= 256;//最后一个字节无需补高位
        }
        String str = Integer.toBinaryString(temp);
        if (flag){
            return str.substring(str.length() - 8);
        }else {
            return str;
        }
    }

    //编写一个方法，将字符串对应的byte[]数组，通过生成的哈夫曼编码表，返回一个哈夫曼编码压缩后的bytes[]

    /**
     *
     * @param bytes
     * @param huffmanCodes 生成的哈夫曼编码
     * @return 返回的是原字符串压缩过后的字节数组
     */
    private static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCodes){
        System.out.println(bytes.length);
            StringBuilder stringBuilder = new StringBuilder();
            for (byte b:bytes){
                stringBuilder.append(huffmanCodes.get(b));
            }
        System.out.println(stringBuilder.toString()+"\t"+stringBuilder.length());
            int len = (stringBuilder.length()+7)/8;

            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;

            for (int i = 0; i < stringBuilder.length(); i += 8){//因为是每八位一个byte,所以步长+8
                String strByte;
                if (i+8 > stringBuilder.length()){
                    strByte = stringBuilder.substring(i);
                }else {
                    strByte = stringBuilder.substring(i, i + 8);//前包后不包
                }
                //将strByte 转换成一个byte，放入到huffmanCodeBytes
                huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte,2);
                index++;
            }
            return huffmanCodeBytes;
    }



    //生成哈夫曼编码
    /*
    * 1、将哈夫曼编码表存放在Map<Byte,String> 形式
    * 2、在生成哈夫曼编码表示，需要去拼接路径，定义一个StringBuilder存储某个叶子节点的路径
    *
    * */
    static Map<Byte,String> huffmanCodes = new HashMap<Byte, String>();
    static StringBuilder stringBuilder = new StringBuilder();

    public static void getCodes(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if (node!=null){
            if (node.data==null){
                //向左递归
                getCodes(node.left,"0",stringBuilder2);
                //向右递归
                getCodes(node.right,"1",stringBuilder2);
            }else {
                //叶子节点 表示找到了最后
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }
    }

    /**
     * 接受一个字节数组
     * @param bytes
     * @return
     */
    public static List<Node> getNodes(byte[] bytes){
        //创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<>();

        //遍历bytes，统计每一个byte出现的次数-》map<key,value>
        Map<Byte,Integer> counts = new HashMap<>();
        for (byte b:bytes){
            Integer count = counts.get(b);
            if (count ==null){
                counts.put(b,1);
            }else {
                counts.put(b,count+1);
            }
        }
        //把每一个键值对转成一个Node对象，并加入到nodes集合中
        for (Map.Entry<Byte,Integer> entry:counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    //编写一个前序遍历的方法
    public static void preOrder(Node node){
        if (node!=null){
            node.preOrder();
        }
    }

    //编写将文件压缩的方法

    /**
     *
     * @param srcFile 你传入的希望压缩的文件的全路径
     * @param dstFile 我们压缩后将压缩文件放到哪个目录
     */
    public static void zipFile(String srcFile,String dstFile){
        FileInputStream is = null;
        OutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b  = new byte[is.available()];
            //读取文件 将字节流的字节放入到这个字节数组中
            is.read(b);
            //获取到文件对应的哈夫曼对应表
            byte[] huffmanBytes = huffmanZip(b);
            //创建文件输出流，存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutStream
            oos = new ObjectOutputStream(os);//对象输出流
            //这里以对象流的方式写入哈夫曼编码，是为了以后我们恢复源文件时使用
            oos.writeObject(huffmanBytes);//我们是把哈夫曼编码后的字节数组写入压缩文件

            //注意一定要把哈夫曼编码写入压缩文件
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public static void unZipFile(String zipFile,String dstFile){
        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;

        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和is关联对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组 huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取哈夫曼编码表
            Map<Byte,String> huffmanCodes = (Map<Byte, String>) ois.readObject();


            //解码
            byte[] bytes = decode(huffmanCodes,huffmanBytes);
            //将bytes数组写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到文件中
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            ;

        }
    }




    static class Node implements Comparable<Node>{
        Byte data;//存放数据本身，比如'a'=>97 ' '(空格) => 32
        int weight;//权值，字符出现的次数
        Node left;
        Node right;

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }

        public void preOrder(){
            System.out.println(this);
            if (this.left!=null){
                this.left.preOrder();
            }
            if (this.right!=null){
                this.right.preOrder();
            }
        }
    }

    //重载getCodes
    private static Map<Byte,String> getCodes(Node root){
        if (root==null){
            return null;
        }
        getCodes(root.left,"0",stringBuilder);
        getCodes(root.right,"1",stringBuilder);
        return huffmanCodes;
    }

    public static Node creatHuffmanTree(List<Node> nodes){
        while (nodes.size()>1){
            Collections.sort(nodes);
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            Node finalNode = new Node(null,left.weight+right.weight);
            finalNode.setLeft(left);
            finalNode.setRight(right);
            nodes.add(finalNode);
            nodes.remove(right);
            nodes.remove(left);
        }
        return nodes.get(0);
    }
}
